#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2020/6/10 14:28
# @USER    : Shengji He
# @File    : LongestValidParentheses.py
# @Software: PyCharm
# @Version  : Python-
# @TASK:
"""
- String
- Dynamic Programming
- Stack
"""


class Stack:
    def __init__(self):
        self.__list = []

    def push(self, value):
        self.__list.append(value)

    def pop(self):
        if self.is_empty():
            raise LookupError('Stack is empty!')
        else:
            self.__list.pop()

    def is_empty(self):
        return not bool(self.__list)

    def top(self):
        if self.is_empty():
            raise LookupError('Stack is empty!')
        else:
            return self.__list[-1]


class Solution:
    """
    Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

    Example 1:
        Input: "(()"
        Output: 2
        Explanation: The longest valid parentheses substring is "()"

    Example 2:
        Input: ")()())"
        Output: 4
        Explanation: The longest valid parentheses substring is "()()"

    Example 3:
        Input: s = ""
        Output: 0

    Constraints:
        - 0 <= s.length <= 3 * 10^4
        - s[i] is '(', or ')'.
    """

    def longestValidParentheses(self, s: str) -> int:
        """

        :param s: str
        :return: int
        """
        # way 1
        # if s.count('(') == 0 or s.count(')') == 0:
        #     return 0
        # ans = 0
        # while s.count('(') > 0 and s.count(')') > 0:
        #     s = s[s.index('('): len(s) - s[::-1].index(')')]
        #     if len(s) == 0:
        #         break
        #     rp = s.index(')')
        #     lp = rp - 1
        #     lans = 0
        #     rans = 0
        #     rmarked = {'(': 0, ')': 0}
        #     while lp >= -1 and rp < len(s):
        #         if s[rp] == ')':
        #             if rmarked['('] > 0:
        #                 rmarked['('] -= 1
        #                 rans += 2
        #                 if rmarked['('] == 0:
        #                     lans += rans
        #                     rans = 0
        #                 rp += 1
        #             elif s[lp] == '(':
        #                 lans += 2 + rans
        #                 rans = 0
        #                 lp -= 1
        #                 rp += 1
        #             else:
        #                 s = s[rp:]
        #                 break
        #         elif s[rp] == '(':
        #             rmarked['('] += 1
        #             rp += 1
        #     if lans > ans:
        #         ans = lans
        #     # if lans > rans:
        #     #     break
        #     s = s[s.index(')') + 1:]
        # return ans

        # way 3
        max_ans = 0
        marked = {'(': 0, ')': 0}
        for ele in list(s):
            marked[ele] += 1
            if marked['('] == marked[')']:
                max_ans = max([max_ans, 2 * marked[')']])
            elif marked[')'] >= marked['(']:
                marked['('] = marked[')'] = 0
        s = s[::-1]
        marked = {'(': 0, ')': 0}
        for ele in list(s):
            marked[ele] += 1
            if marked['('] == marked[')']:
                max_ans = max([max_ans, 2 * marked[')']])
            elif marked['('] >= marked[')']:
                marked['('] = marked[')'] = 0
        return max_ans

    def longestValidParentheses_stack(self, s: str) -> int:
        # way 2
        max_ans = 0
        stack = Stack()
        stack.push(-1)
        for i in range(len(s)):
            if s[i] == '(':
                stack.push(i)
            else:
                stack.pop()
                if stack.is_empty():
                    stack.push(i)
                else:
                    max_ans = max([max_ans, i - stack.top()])
        return max_ans

    def longestValidParentheses_dp(self, s: str) -> int:
        max_len = 0
        dp = [0] * len(s)
        for i in range(1, len(s)):
            if s[i] == ')':
                if s[i - 1] == '(':
                    dp[i] = (dp[i - 2] if i >= 2 else 0) + 2
                else:
                    pre_len = dp[i - 1]
                    pre_index = i - pre_len - 1
                    if pre_index >= 0 and s[pre_index] == '(':
                        dp[i] = dp[i - 1] + 2
                        if pre_index >= 1:
                            dp[i] += dp[pre_index - 1]
                max_len = max(max_len, dp[i])
        return max_len


if __name__ == '__main__':
    S = Solution()
    # s = ")(())))(())())"
    s = "()((())()"
    # s = "(())()(()(("
    # s = ")("
    # s = ")(((((()())()()))()(()))("
    # s = "()(()"
    # s = ")()())()()("
    # s = "((((((((("
    # s = ")()())"
    # s = "(()"
    print(S.longestValidParentheses(s))
    print(S.longestValidParentheses_stack(s))
    print(S.longestValidParentheses_dp(s))
    print('done')
